// https://leetcode.cn/problems/populating-next-right-pointers-in-each-node/
// Created by ade on 2022/7/21.
//
#include <iostream>
#include <vector>
#include <map>


using namespace std;

struct Node {
    int val;
    Node *left;
    Node *right;
    Node *next;
}

/*
 *                            1
 *                   2                3
 *              4        5        6        7
 *           8     9  10   11  13  14  15     16
 *
 * */

class Solution {
public:
    map<int, Node*> myMap;
    Node *connect(Node *root) {
        if (!root || !root->left) return root;
        dfs(root, 0);
        return root;
    }

    void dfs(Node* node, int index) {
        if (node) {
            if (myMap[index] != nullptr) {
                myMap[index]->next = node;
            }
            myMap[index] = node;
            dfs(node->left, index + 1);
            dfs(node->right, index + 1);
        }
    }
};

int main() {
    Solution so;
    TreeNode *head = so.init();
    so.pruneTree(head);
    so.show(head);
    return 0;
}